package leetcode_901_1000;

public class LeeCode_980 {
    public static void main(String[] args) {
        System.out.println(uniquePathsIII(new int[][]{{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}}));
    }

    private static int uniquePathsIII(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        int x = 0, y = 0, count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                } else if (grid[i][j] == 0) {
                    count++;
                } else if (grid[i][j] == -1){
                    vis[i][j] = true;
                }
            }
        }
        vis[x][y] = true;
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[] ans = new int[1];
        dfs(vis, grid, dirs, ans, x, y, 0, count);
        return ans[0];
    }

    private static void dfs(boolean[][] vis, int[][] grid, int[][] dirs, int[] ans, int i, int j, int count, int goal) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid[i][j] == 2) {
            if (count == goal + 1)
                ans[0]++;
            return;
        }
        vis[i][j] = true;
        for (int[] dir : dirs) {
            int nx = i + dir[0];
            int ny = j + dir[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny])
                continue;
            dfs(vis, grid, dirs, ans, nx, ny, count + 1, goal);
        }
        vis[i][j] = false;
    }
}